package q648_replaceWords;

import java.util.HashMap;
import java.util.List;
import java.util.Map;


class Trie {
    Map<Character, Trie> children;

    public Trie() {
        children = new HashMap<>();
    }
}


public class Solution_2 {
    /*
    使用字典树的另一种写法来解决该问题
    考虑将字典数变为一个由map来连接的方式
    首先将所有的dict中单词加入到字典树中，并且使用一个特殊符号# 用来记录一个单词的结尾
    然后对于sentence中的所有单词
    考察其中字符是否按顺序出现在字典树中，判断顺序应该是
    1 遇到# 代表此时有一条路径已经走完 直接返回此时的root即可
    2 此时的字符没有被树记录 意味着该单词在树中没有对应前缀 直接返回该单词
    3 否则就加入当前字符 然后将树跳转到对应字符的下一棵树
     */
    public String replaceWords(List<String> dictionary, String sentence) {
        Trie trie = new Trie();
        for (String word : dictionary) {
            Trie cur = trie;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                cur.children.putIfAbsent(c, new Trie());
                cur = cur.children.get(c);
            }
            // 使用一个特殊标记结尾
            cur.children.put('#', new Trie());
        }
        String[] words = sentence.split(" ");
        for (int i = 0; i < words.length; i++) {
            words[i] = findRoot(words[i], trie);
        }
        return String.join(" ", words);
    }

    public String findRoot(String word, Trie trie) {
        StringBuilder root = new StringBuilder();
        Trie cur = trie;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (cur.children.containsKey('#')) {
                return root.toString();
            }
            if (!cur.children.containsKey(c)) {
                return word;
            }
            root.append(c);
            cur = cur.children.get(c);
        }
        return root.toString();
    }
}


